package com.kevinkk.dp;

/**
 * 给你一个非负整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 *
 * 求方法都是采用 dp[j] += dp[j - nums[i]] 的递推公式 ‼️
 */

/**
 * left + right = sum
 * left - right = target
 * target = left = (sum + target) / 2
 *
 * 将 nums 中的数字装入容量为 target 的背包中，期待其价值为 target，求有多少种方法
 *
 * 1. dp 数组含义：dp[j] 背包容量为 j 时有多少种装物品的方法
 * 2. dp 公式：dp[j] += dp[j - nums[i]]
 *      dp[j] 可以是 dp[j - nums[0]] 然后再装入一个 nums[0]，也可以是dp[j - nums[1]] 然后再装入一个 nums[1]...
 * 3. 初始化：dp[0] 必须初始化为 1、不能是0，否则后续计算的所有值都为 0
 * 4. 遍历顺序：一维dp，并且是每个物品只能用一次，因此，先遍历物品、再遍历背包，背包采用倒序号遍历
 */

public class TargetSum {
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for(int i : nums) sum += i;
            // 直接无法满足情况
            if(target > sum || (sum + target) % 2 == 1) return 0;
            target = (sum + target) / 2;
            int[] dp = new int[target+1];
            dp[0] = 1;

            for(int i = 0; i < nums.length; i++){
                for(int j = target; j >= nums[i]; j--){
                    dp[j] += dp[j-nums[i]];
                }
            }

            return dp[target];

        }
    }
}
